//
// Created by liushuai on 18-9-11.
//

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10005;
int edge[maxn][maxn];//edge[i][j] == 1 代表i，j可以匹配
//int visited[maxn];//用来记录该点是否被访问过
bool *visited = new bool[maxn];
int *cx = new int[maxn];
int *cy = new int[maxn];//用来记录x集合中匹配的y元素是哪个;
int nx, ny;//nx表示x集合的顶点个数， ny表示y集合的顶点个数

bool DFS(int u){
    int v;
    for(v = 0; v < ny; v++){
         if(edge[u][v] && !visited[v]){
            visited[v] = true;
            if(cy[v] == 0 || DFS(cy[v])){//如果y集合中的v没有匹配或v已经匹配，但从cy[v]中可以找到一条增广路
                cx[u] = v;//找到增广路，修改匹配
                cy[v] = u;
                return true;
            }
        }
    }
    return false;
}

int maxmatch(){
    int sum = 0, i;
    for(i = 0; i <= nx; i++){
        if(cx[i] == 0){//还没被匹配就执行内部代码
            sum += DFS(i);//以 i 为起点开始查找增广路，返回true ，匹配数+1
        }
    }
    return sum;
}

int main(){
    int x, y, relate;
    cout<<"输入边数： "<<endl;
    while(cin>>relate){
        cout<<"输入集合x,y元素数量:"<<"\n";
        cin>>nx>>ny;
        memset(edge, 0, sizeof(edge));
        for(int i = 0; i < relate; i++){
            cin>>x>>y;
            edge[x][y] = 1;
        }
        int sum = maxmatch();
        cout<<"最大匹配边数: "<<sum<<"\n";
    }
    delete [] cx;
    delete [] cy;
    delete [] visited;
    return 0;
}